import java.util.Arrays;

/**
 * @author caesar
 * @date 2025/7/1
 * @apiNote
 */
/*
快速排序整理思路：


*/
public class quicksork {
    public static void main(String[] args) {
        int[] arr = {6, 3, 7, 1, 9, 4};
        System.out.println(Arrays.toString(quickSort(arr, 0, arr.length - 1)));
    }

    public static int[] quickSort(int[] arr, int left, int right) {
        int i, j, temp, t;
        if (left > right) {
            return null;
        }
        i = left;
        j = right;
        temp = arr[left];//基准位
        while (i < j) {
            //先从右边将j依次往左移动
            while (arr[j] >= temp && i < j) {
                j--;
            }
            //再从左边将i依次往右移动
            while (arr[i] <= temp && i < j) {
                i++;
            }
            //满足条件则交换
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        //最后将基准元素为与i和j相等位置的元素交换
        arr[left] = arr[i];
        arr[i] = temp;

        quickSort(arr, left, j - 1);//递归调用左半数组
        quickSort(arr, j + 1, right);//递归调用左半数组
        return arr;
    }
}
